package 链表;

/**
 * @ClassName:SimpleMain
 * @Description: 简单链表练习
 * @Author:Deamer
 * @Date:2022/1/16 21:14
 **/
public class SimpleMain {
    public static void main(String[] args) {
        ListNode head = new ListNode(5);
        head.next = new ListNode(4);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(2);
        head.next.next.next.next = new ListNode(1);
        ListNode tmpNode = head;
        System.out.println("转换之前：");
        while (head != null) {
            System.out.print(head.val + "\t");
            head = head.next;
        }
        ListNode newNode = middleNode(tmpNode);
        System.out.println();
        System.out.println("转换之后：");
        while (newNode != null) {
            System.out.print(newNode.val + "\t");
            newNode = newNode.next;
        }
    }

    /**
     * 876. 链表的中间结点
     * https://leetcode-cn.com/problems/middle-of-the-linked-list/
     * 方法3：快慢指针
     * 快指针比慢指针快走的2倍  慢指针：X 快指针：Y Y=Y+2*N；X=X+N
     */
    // 时间复杂度：O(n) 空间复杂度：O(1)
    public static ListNode middleNode3(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 876. 链表的中间结点
     * https://leetcode-cn.com/problems/middle-of-the-linked-list/
     * 方法2：单指针
     * 首先计算出链表中元素的个数N，再遍历链表取N/2的元素（0为头节点下标）
     */
    // 时间复杂度：O(n) 空间复杂度：O(1)
    public static ListNode middleNode2(ListNode head) {
        if (head.next == null) {
            return head;
        }
        int count = 1;
        ListNode tmp = head;
        while (tmp.next != null) {
            count++;
            tmp = tmp.next;
        }
        for (int i = 0; i < count / 2; i++) {
            head = head.next;
        }
        return head;
    }

    /**
     * 876. 链表的中间结点
     * https://leetcode-cn.com/problems/middle-of-the-linked-list/
     * 方法1：数组
     * 遍历链表，将元素放入到数组中，取数组的中间N/2(不可取，需要初始化一个数组大小，此大小不确定)
     */
    // 时间复杂度：O(n) 空间复杂度：O(n)
    public static ListNode middleNode(ListNode head) {
        if (head.next == null) {
            return head;
        }
        ListNode[] listNodes = new ListNode[100];
        int i = 0;
        while (head != null) {
            listNodes[i++] = head;
            head = head.next;
        }
        return listNodes[i / 2];
    }

    /**
     * 83. 删除排序链表中的重复元素
     * https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
     * 方法：一次遍历
     */
    // 时间复杂度：O(n) 空间复杂度：O(1)
    public static ListNode deleteDuplicates2(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode cur = head;// 当前节点
        while (cur.next != null) {
            int val = cur.val;
            if (val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }

    /**
     * 83. 删除排序链表中的重复元素
     * https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
     * 自己实现：迭代（利用虚拟节点）
     */
    // 时间复杂度：O(n) 空间复杂度：O(1)
    public static ListNode deleteDuplicates(ListNode head) {
        ListNode returnNode = new ListNode(0);
        returnNode.next = head;
        ListNode tmp = returnNode;
        while (tmp.next != null && tmp.next.next != null) {
            int val = tmp.next.val;
            if (val == tmp.next.next.val) {
                // 删节点
                tmp.next = tmp.next.next;
            } else {
                tmp = tmp.next;
            }
        }
        return returnNode.next;
    }

    /**
     * 203. 移除链表元素
     * https://leetcode-cn.com/problems/remove-linked-list-elements/
     * 方法一：递归
     *
     * @param head
     * @param val
     * @return
     */
    // 时间复杂度：O(n) 空间复杂度：O(n)
    public static ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return head;
        }
        // 遍历的当前节点处理
        head.next = removeElements(head.next, val);
        // 如果查到要删除的元素，返回下一个节点，即删除
        return head.val == val ? head.next : head;
    }

    /**
     * 203. 移除链表元素
     * https://leetcode-cn.com/problems/remove-linked-list-elements/
     * 方法二：迭代（利用虚拟节点）
     *
     * @param head
     * @param val
     * @return
     */
    // 时间复杂度：O(n) 空间复杂度：O(1)
    public static ListNode removeElements2(ListNode head, int val) {
        ListNode returnNode = new ListNode(0);
        returnNode.next = head;
        ListNode tmp = returnNode;// temp 表示当前节点
        while (tmp.next != null) {
            if (tmp.next.val == val) {
                tmp.next = tmp.next.next;
            } else {
                tmp = tmp.next;
            }
        }
        return returnNode.next;
    }

    /**
     * https://leetcode-cn.com/problems/delete-node-in-a-linked-list/
     * 237. 删除链表中的节点
     */

    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }

    /**
     * https://leetcode-cn.com/problems/reverse-linked-list/
     * 206. 反转链表
     */
    // 例如：5》4》3》2》1》null反转成：1》2》3》4》5》null
    // 递归方法：节点反转。先把头结点下一个节点进行向下遍历，最后处理头节点和返回后的那部分节点
    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 反转是：1》2》3》4》
        ListNode newListNode = reverseList(head.next);
        // 让4的指针指向5
        head.next.next = head;
        // 5的指针下个节点是null
        head.next = null;
        return newListNode;
    }

    // 非递归方法：指针指向反转。将头节点的指针指向null，将链表向下遍历，newHead是处理后的头节点，tmp存取下一个节点
    public static ListNode reverseList2(ListNode head) {
        ListNode newHead = null;
        while (head != null) {
            ListNode tmp = head.next;
            head.next = newHead;
            newHead = head;
            head = tmp;
        }
        return newHead;
    }

    /**
     * 141. 环形链表
     * 判断一个链表中是否有环
     * https://leetcode-cn.com/problems/linked-list-cycle/
     */
    public static boolean hasCycle(ListNode head) {
        if (null == head || null == head.next) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        // 快走两步，如果不常很大的话容易错过，不安全
        while (null != fast && null != fast.next) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
}
